#ifndef _NODE_CONTAINER_H
#define _NODE_CONTAINER_H

#include<stdlib.h>

#include<tools/lb_memory.h>
#ifdef __cplusplus
extern "C"{
#endif


typedef struct Node
{
    void* Prev;
    void* value;
    void*  Next;
    void* traits;

}Node;


static inline void Node_init(Node*node)
{
    node->Prev=NULL;
    node->Next=NULL;
    node->value=NULL;
    node->traits=NULL;
}
//void Node_init(Node*);

Node* node_prev(Node*node);
Node* node_next(Node*node);

void free_node(Node*);
void free_node_value(Node*);

Node* node_find(Node*,void*);

Node* node_findr(Node*,void*);

Node* node_copy(Node*);
int node_size(Node*);
Node* node_at(Node* ,int);

static inline Node* node_overlying(Node*node,void *value)
{
    Node* node1=(Node*)LB_MALLOC(sizeof(Node));
    Node_init(node1);
    node1->value=value;
    node1->Next=node;
    if(node!=NULL)
    {
        node->Prev=node1;

    }
    return node1;

}
static inline Node* node_pushback(Node* node,void* value)
{
    Node* node1=(Node*)LB_MALLOC(sizeof(Node));
    Node_init(node1);
    node1->value=value;
    node1->Prev=node;
    if(node!=NULL)
    {
        node->Next=node1;
    }
    return node1;

}
/***************
 * node_reverse 不返回新的链表，只返回新的位置
 * node_reversen返回新的链表
**********/
Node* node_reverse(Node*);
Node* node_reversen(Node*);

//return the new created node
static inline Node* node_insertback(Node*nit,void*value)
{
    if(nit==NULL)
    {
        return NULL;
    }
    Node* node=(Node*)LB_MALLOC(sizeof(Node));
    Node_init(node);

    node->value=value;
    node->Next= nit->Next;
    if(nit->Next!=NULL)
    {
        ((Node*)(nit->Next))->Prev=node;
    }
    node->Prev=nit;
    nit->Next=node;
    return node;
}

static inline void node_eliminate(Node* node)
{
    if(node==NULL)
    {
        return;
    }
    Node* node1=(Node*)(node->Prev),*node2=(Node*)(node->Next);
    if(node1!=NULL)
    {
        node1->Next=(void*)node2;
    }
    if(node2!=NULL)
    {
        node2->Prev=(void*)node1;
    }
    LB_FREE(node);
}

// 不释放n内存,只移除关系
//
static inline Node* node_removen(Node*node,Node*n)
{
    if(node==NULL||n==NULL)
    {
        return node;
    }
    Node* re=node;
    if(node==n)
    {
        re=(Node*)(node->Next);
    }

    Node* node1=(Node*)(n->Prev),*node2=(Node*)(n->Next);
    if(node1!=NULL)
    {
        node1->Next=(void*)node2;
    }
    if(node2!=NULL)
    {
        node2->Prev=(void*)node1;
    }

    return re;
}


static inline Node* node_remove(Node*node,Node*n)
{
    if(node==NULL||n==NULL)
    {
        return node;
    }
    Node* re=node;
    if(node==n)
    {
        re=(Node*)(node->Next);
    }
    node_eliminate(n);
    return re;
}


// static inline Node* node_insert_back_value(Node*node,void* v)
// {

//     Node* re=node;



//     return re;
// }
//given a value,find the node and remove it from list

static inline Node* node_delete_value(Node* node,void* value)
{
    if(node==NULL){return NULL;}
    Node* node1=node_find(node,value);
    Node* re=node;
    if(node1==NULL){   return re;}
    if(node1->Prev==NULL){re=(Node*)node1->Next;}
    node_eliminate(node1);
    return re;
}
static inline Node* node_plus(Node*n1,Node*n2)
{
    if(n1==NULL)
    {return n2;}
    else if(n2==NULL)
    {
        return n1;
    }
    Node* l3=node_reverse(n1);
    l3->Next=(void*)n2;
    n2->Prev=(void*)l3;
    return n1;
}

//*********
// 该返回结果将创建新的链表
//*******
static inline Node* node_splicingn(Node*n1,Node*n2)
{
    Node* l1=node_copy(n1);
    Node* l2=node_copy(n2);
    if(l1==NULL)
    {return l2;}
    else if(l2==NULL)
    {
        return l1;
    }
    Node* l3=node_reverse(l1);
    l3->Next=(void*)l2;
    l2->Prev=(void*)l3;
    return l1;

}

Node* node_union(Node*n1,Node*n2);

Node* node_intersection(Node* n1,Node* n2);

Node* node_minus(Node* n1,Node* n2);

Node* node_bub_sort(Node* n,int (*cmp)(void* a,void* b));
//
//对n改变
//
Node* node_bub_sortn(Node* n,int (*cmp)(void* a,void* b));
//
//对n不改变,返回新的链表
//
Node* node_quick_sort(Node* n,int (*cmp)(void* a,void* b));

Node* node_filter_condition(Node* n,int (*filter_condition)(void* a));
void ** node2array(Node*n,int* len);
Node* array2node(void**data,int len);
//对链表进行唯一化操作
Node* unique_node(Node* n);


typedef struct LB_List{
    Node* first;
    Node* end;
    int size;
}LB_List;

static inline void lb_list_init(LB_List* ll)
{
    ll->first=NULL;
    ll->end=NULL;
    ll->size=0;
}

static inline void lb_list_push_back(LB_List*ll,void*data)
{
    if(ll->first==NULL)
    {
        ll->first=node_pushback(NULL,data);
        ll->end=ll->first;
    }
    else
    {
        if(ll->end==NULL)
        {
            ll->end=ll->first;
            ll->end->value=data;
        }
        else
        {
            if(ll->end->Next==NULL)
            {
                ll->end=node_pushback(ll->end,data);
            }
            else
            {
                ll->end=(Node*)(ll->end->Next);
                ll->end->value=data;
            }
        }
    }

    ll->size++;
}


static inline void* lb_list_pop(LB_List*ll)
{
    if(ll->end==NULL){return NULL;}
    void * re=ll->end->value;
    ll->end=(Node*)(ll->end->Prev);

    ll->size--;
    return re;
}

static   inline  void lb_list_clear(LB_List*ll)
{
    free_node(ll->first );
}

#ifdef __cplusplus
}
#endif
#endif
